/*
https://leetcode-cn.com/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/solution/zhao-dao-zui-xiao-sheng-cheng-shu-li-de-gu57q/
 */
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Solution1489 {
    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
        List<int[]> list=new ArrayList<>();
        for (int i=0;i<edges.length;i++){
            list.add(new int[]{i,edges[i][0],edges[i][1],edges[i][2]});
        }
        list.sort(Comparator.comparingInt(a -> a[3]));
        int[] b=new int[n];
        for (int i=0;i<n;i++){
            b[i]=i;
        }
        int v=0;
        for (int[] ints : list) {
            int x=find(b,ints[1]);
            int y=find(b,ints[2]);
            if (x!=y){
                v=v+ints[3];
                b[x]=y;
            }
        }
        List<List<Integer>> ans=new ArrayList<>();
        ans.add(new ArrayList<>());
        ans.add(new ArrayList<>());
        for (int i=0;i<list.size();i++){
            int value=0;
            int[] nb=new int[n];
            for (int k=0;k<n;k++){
                nb[k]=k;
            }
            int size=n;
            for (int j=0;j<list.size();j++){
                if (i==j){
                    continue;
                }
                int[] ints=list.get(j);
                int x=find(nb,ints[1]);
                int y=find(nb,ints[2]);
                if (x!=y){
                    value=value+ints[3];
                    nb[x]=y;
                    size--;
                }
            }
            if (size!=1 || size==1 && value > v){
                ans.get(0).add(list.get(i)[0]);
                continue;
            }
            nb=new int[n];
            for (int k=0;k<n;k++){
                nb[k]=k;
            }
            size=n-1;
            nb[list.get(i)[1]]=nb[list.get(i)[2]];
            value=list.get(i)[3];
            for (int j=0;j<list.size();j++){
                if (i==j){
                    continue;
                }
                int[] ints=list.get(j);
                int x=find(nb,ints[1]);
                int y=find(nb,ints[2]);
                if (x!=y){
                    value=value+ints[3];
                    nb[x]=y;
                    size--;
                }
            }
            if (size==1 && value == v){
                ans.get(1).add(list.get(i)[0]);
            }
        }
        return ans;
    }

    private int find(int[] b, int i) {
        while (i!=b[i]){
            i=b[i];
        }
        return i;
    }

    public static void main(String[] args) {
        for (List<Integer> criticalAndPseudoCriticalEdge : new Solution1489().findCriticalAndPseudoCriticalEdges(5, new int[][]{{0, 1, 1}, {1, 2, 1}, {2, 3, 2}, {0, 3, 2}, {0, 4, 3}, {3, 4, 3}, {1, 4, 6}})) {
            System.out.println(criticalAndPseudoCriticalEdge);
        }
    }
}
